package cn.bellychang.leetcode.question225;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Implement a last in first out (LIFO) stack using only two queues.
 * The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).
 *
 *
 *
 * @author ChangLiang
 * @date 2021/1/28
 */
public class MyStack {

    private Deque<Integer> queueA;

    private Deque<Integer> queueB;

    private int count;

    /** Initialize your data structure here. */
    public MyStack() {
        queueA = new ArrayDeque<>();
        queueB = new ArrayDeque<>();
        count = 0;
    }

    /** Push element x onto stack. */
    public void push(int x) {
        if (count == 0) {
            queueA.add(x);
        } else {
            for (int i = 0; i < count; i++) {
                queueB.add(queueA.remove());
            }
            queueA.add(x);
            for (int i = 0; i < count; i++) {
                queueA.add(queueB.remove());
            }
        }
        count++;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        count--;
        return queueA.remove();
    }

    /** Get the top element. */
    public int top() {
        return queueA.element();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return count==0;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        int[] temp = new int[count];
        int index = count - 1;
        for (int i = 0; i < count; i++) {
            Integer remove = queueA.remove();
            temp[index--] = remove;
        }

        for (int i = 0; i < count; i++) {
            builder.append(temp[i]).append("->");
        }

        for (int i = count - 1; i >= 0; i--) {
            // 补偿回去
            queueA.add(temp[i]);
        }

        return builder.toString().endsWith("->") ?
                builder.substring(0, builder.length() - 2) :
                builder.toString();

    }
}
